package leetcode_题库;

import java.util.*;

/**
 * Created by IntelliJ IDEA.
 *
 * @Author : Ding
 * @create 2022/8/16 16:22
 */
public class _5_最长回文子串 {

    public static void main(String[] args) {
        //测试用例
        String s = "aacabdkacaa";

        //转字符数组
        char[] str = s.toCharArray();
        //存储结果
        String ret = str.length > 0 ? str[0] + "" : "";
        //存储结果
        LinkedList<Character> list = new LinkedList<>();
        //遍历原字符串
        for (int i = 0; i < str.length; i++) {
            //存储每次遍历的子项
            Character item = str[i];
            //遍历在已存在数组中，值为item的角标集合
            LinkedList<Integer> index = new LinkedList<>();
            for (int j = 0; j < list.size(); j++) {
                if (str[j] == item){
                    index.add(j);
                }
            }
            //倘若index长度大于0，说明存在
            System.out.println(item+"有："+index.size());
            try {
                Thread.sleep(100);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            if (index.size() > 0){
                //我们遍历n种情况（先从最左侧开始，也就是最大宽度，如果合适了就break，尽量不让程序达到O(n3)）
                for (int k = 0; k < index.size(); k++) {
                    //创建一个新的临时序列
                    StringBuilder temp = new StringBuilder();
                    for (int j = index.get(k); j < list.size(); j++) {
                        temp.append(str[j]);
                    }
                    temp.append(item);
                    //第一次插入完毕，判定它是不是对称的
                    char[] tempChar = temp.toString().toCharArray();
                    int leftPointer = tempChar.length / 2 - 1;
                    int rightPointer = tempChar.length % 2 == 1? tempChar.length / 2 + 1 : tempChar.length / 2;
                    boolean isSymmetry = true;
                    while (leftPointer >= 0){
                        if (tempChar[leftPointer--] != tempChar[rightPointer++]){
                            isSymmetry = false;
                            break;
                        }
                    }
                    System.err.println(temp+" :"+isSymmetry);
                    if (isSymmetry){
                        //可以，直接退出
                        ret = temp.length() > ret.length() ? String.valueOf(temp) : ret;
                        break;
                    }
                }
            }
            //追加
            list.add(item);
        }
        System.err.println(ret);

    }

    /*

    //存储结果字符串
        String ret = s.charAt(0) + "";
        //存储有序set
        LinkedHashSet<Character> set = new LinkedHashSet<>();
        //遍历原字符串
        for (int i = 0; i < s.length(); i++) {
            //如果set中存在当前字符
            if (set.contains(s.charAt(i))){
                //如果set的长度还大于ret的长度
                if (set.size() + 1 > ret.length()){
                    ret = "";
                    boolean isFind = false;
                    for (Character character : set) {
                        if (!isFind){
                            if (character.equals(s.charAt(i))){
                                isFind = true;
                            }else{
                                continue;
                            }
                        }
                        ret += character;
                    }
                    ret += s.charAt(i);
                }
            }
            set.add(s.charAt(i));
        }
        System.err.println(ret);


     */
}
